Introduction to Hidden markov Model
Application to movement ecology
2024-12-09
Movement Ecology Paradigm
[Nat+08] presents individual movement as the result of:
- Motion capacities
- Internal state
- Environment
Movement informs on internal states and habitat preferences
From Movement to Movement Data
From Movement to Movement Data
From Movement to Movement Data
From Movement to Movement Data
Description
Ecological question: Identifying various movement patterns
Rarely in a supervised context
Mostly unsupervised
From Movement Data to Movement Model
Often analysed using discrete time model and typically Hidden Markov Model
Heterogeneity in movement pattern interpretated as different internal states
Heterogeneity in movement pattern interpretated as different internal states
Accounting for internal states
- Change point detection approach. based on [Pic+07]
\[\left .\begin{array}{c} Y_{1k} \sim f(\theta_{1\ell})\\ Y_{2k} \sim f(\theta_{2\ell}) \end{array} \right\rbrace \mbox{ if } k \mbox{ in region }I_{\ell}=[\tau_{\ell-1}+1,\tau_{\ell}]\]
The best segmentation for a given number of change points L: \[argmin_{0< \tau_1 < \ldots < \tau_L} C(\boldsymbol{Y}) \]
Brute force complexity : \(O(N^L)\),
Dynamic Programming algorithm complexity : \(O(N^2)\) or even less with pruning strategy
Limitation in the choice for \(f.\)
Mixture model as a simple Latent variables model
Assume that the numer of states \(K\) is known
- Modelling \(Z\): \(\pi_k={\mathbb{P}}(Z_i=k), \quad k=1,\ldots, K, \quad \sum_k \pi_k=1\)
- \(Z_i \overset{i.i.d}{\sim} \mathcal{M}(1, \boldsymbol{\pi}), \quad P(Z_{ik}=1)=\pi_k\)
- Modelling \(Y\)}: The \(Y_i's\) are assumed to be independent conditionnaly to \({\boldsymbol{Z}}\) : \((Y_i\vert Z_i = k) \overset{i.i.d}{\sim} f_{\gamma_k}().\)
Model parameters \(\boldsymbol{\theta}=(\boldsymbol{\pi}, \boldsymbol{\gamma})\) 
Statistical inference of incomplete data models
Goal :
\[(\widehat{\boldsymbol{\gamma}},\widehat{\boldsymbol{\Pi}}, \widehat{\boldsymbol{\nu}}) = \arg\max_{\boldsymbol{\gamma}, \boldsymbol{\Pi}, {\boldsymbol{\nu}}} \log P({\boldsymbol{Y}}; \boldsymbol{\gamma}, \boldsymbol{\Pi}, \boldsymbol{\nu})\]
\[\log {\mathbb{P}}({\boldsymbol{Y}}; \boldsymbol{\theta}) = \log \sum_{k_1, k_N \in K^N }{\mathbb{P}}({\boldsymbol{Y}}, {\boldsymbol{Z}}= (k_1, \ldots,k_N); \boldsymbol{\theta})\] * No analytical estimators.
It is not always possible to compute since this sum typically involves \(K^n\) terms : \(2^{100}\approx10^{30}\)
Brute force algorithm is not the way
A convenient notation \(Z_{ik}=1\) if \(Z_i=k\)
\[\begin{align} \log {\mathbb{P}}({\boldsymbol{Y}}, {\boldsymbol{Z}}; \boldsymbol{\theta}) & = \class{bleu}{\sum_k Z_{1k} \log \nu_k }\\ &\class{bleu}{+ \sum_{i > 1} \sum_{k, \ell} Z_{i-1,k}Z_{i,\ell} \log \pi_{k\ell}} \\ & + \class{orange}{\sum_i \sum_k Z_{ik} \log f(y_i ; \gamma_k)} \end{align}\]
Idea : replace \(Z_{ik}\) by its best guess
\[\begin{align} {\mathbb{E}}\left( \log {\mathbb{P}}({\boldsymbol{Y}}, {\boldsymbol{Z}}; \boldsymbol{\theta})\vert Y_{1:N}\right) & = \class{bleufonce}{\sum_k{\mathbb{E}}\left( Z_{1k} \vert Y_{1:N}\right) \log \nu_k }\\ & \class{bleufonce}{+ \sum_{i > 1} \sum_{k, \ell} {\mathbb{E}}\left( Z_{i-1,k}Z_{i,\ell}\vert Y_{1:N}\right) \log \pi_{k\ell}} \\ & + \class{rouge}{\sum_i \sum_k {\mathbb{E}}\left(Z_{ik}\vert Y_{1:N}\right) \log f(X_i ; \gamma_k)} \end{align}\]
Expexctation Maximization (EM) algorithm
Bayes Formula
\[\begin{align} {\mathbb{P}}({\boldsymbol{Y}}, {\boldsymbol{Z}};\boldsymbol{\theta}) & = {\mathbb{P}}({\boldsymbol{Y}}\vert {\boldsymbol{Z}}; \boldsymbol{\theta}) P({\boldsymbol{Z}}; \boldsymbol{\theta}),\\ & = {\mathbb{P}}({\boldsymbol{Z}}\vert {\boldsymbol{Y}}; \boldsymbol{\theta}) {\mathbb{P}}({\boldsymbol{Y}}; \boldsymbol{\theta}). \end{align}\]
Therefore, \[\begin{align} \log {\mathbb{P}}({\boldsymbol{Y}}; \boldsymbol{\theta}) & = \log \left \lbrace {\mathbb{P}}({\boldsymbol{Y}}, {\boldsymbol{Z}};\boldsymbol{\theta}) / {\mathbb{P}}({\boldsymbol{Z}}\vert {\boldsymbol{Y}}; \boldsymbol{\theta}) \right\rbrace\\ & = \log {\mathbb{P}}({\boldsymbol{Y}}, {\boldsymbol{Z}};\boldsymbol{\theta}) - \log {\mathbb{P}}({\boldsymbol{Z}}\vert {\boldsymbol{Y}}; \boldsymbol{\theta}) \\ \end{align}\]
For a given \(\boldsymbol{\theta}_0\), we may compute \({\mathbb{P}}_{\boldsymbol{\theta}_0}=P({\boldsymbol{Z}}\vert \boldsymbol{\theta}_0, {\boldsymbol{Y}})\) and \[\begin{align} \log {\mathbb{P}}({\boldsymbol{Y}}; \boldsymbol{\theta}) &= \class{orange}{{\mathbb{E}}_{\boldsymbol{\theta}_0}(\log P({\boldsymbol{Y}}, {\boldsymbol{Z}};\boldsymbol{\theta})\vert {\boldsymbol{Y}})} - {\mathbb{E}}_{\boldsymbol{\theta}_0}(\log {\mathbb{P}}({\boldsymbol{Z}}\vert {\boldsymbol{Y}}; \boldsymbol{\theta})\vert {\boldsymbol{Y}})\\ & = \class{orange}{Q(\boldsymbol{\theta}, \boldsymbol{\theta}_0)} - H(\boldsymbol{\theta}, \boldsymbol{\theta}_0) \end{align}\]